The present invention concerns a method of obtaining a signed binary representation of a number from its binary representation.
Fast arithmetic calculation techniques have for a long time been using the signed binary representation, since it makes it possible to calculate additions, multiplications or divisions very effectively.
Many integrated circuits comprise a device for converting a number into signed binary code from its binary representation and arithmetic calculation devices for performing operations with this operand in signed binary representation. In general, a reverse conversion device is provided, for supplying the result in the binary form.
In signed binary representation, a number is expressed in m digits of values “0”, “1” or “−1”. Several signed binary representations of the same number exist. For example, the number 5 can be written as (1 1 −1), that is to say 1×22+1×21−1×20. However, it can also be written (1 0 1).
Amongst the possible signed binary representations, there exists a remarkable one, known as the Reitwiesner representation. This representation has the particularly interesting characteristics of being unique and hollow and having the smallest Hamming weight.
If the binary representation of the number r is denoted r=(rm−1, . . . , r0), the Reitwiesner signed binary representation, which is denoted r=(r′m, rm−1, . . . , r′2, r′1, r′0), comprises one additional digit.
To state that this representation is hollow means that it satisfies the fact that the multiplication of two adjacent digits is zero, which is written:r′i·r′i−1=0, ∀iε{0, . . . m}. 
The Hamming weight for its part expresses the number of non-zero digits in the representation in question. Having a minimum Hamming weight therefore means an optimum maximum number of digits at “0”. However, the fewer “1” or “−1” digits in the representation, the fewer calculations there are actually to carry out, and hence an improvement in terms of calculation speed. This is therefore a particularly interesting property of the Reitwiesner representation in terms of fast arithmetic calculation.
The algorithm which makes it possible to obtain this remarkable signed binary representation from the binary representation (rm−1, . . . , r0) of a number r, can be described as follows:                A calculation variable c is used, in binary.        The bit c0 of rank 0 of this variable c is initialised to “0”.        There are added, to the binary representation (rm−1, . . . , r0) of the number r, a bit of rank m+1 and a bit of rank m, both initialised to “0”: rm−1=0; rm=0        Then, for i equal to 0 up to i equal to m, the following are calculated:ci+1=└(ci+ri+ri−1)/2┘r′i=ci+ri−2ci−1         where └t┘ means the default value, that is to say the integer value immediately lower than the number t. In practice, as the arithmetic sum of the bits ci+ri+ri+1 is coded in a maximum of two bits in binary, the bit ci+1 is obtained by shifting this sum by one position to the right.        
It can be seen that, in this Reitwiesner algorithm, the bits ri of the binary representation of the number r are processed from right to left, in order to obtain each of the digits r′i of the signed binary representation, from i equals 0 up to i equals m.
Various works were able to show that there was no algorithm in which the bits would be processed from left to right and by means of which the Reitwiesner signed binary representation would be obtained.
However, in many applications, the fast arithmetic calculation algorithms applied to an operand r process the digits r′i in the signed binary representation of this operand from left to right. These algorithms prove in fact, in some cases, to be more effective both with regard to calculation time and on the hardware level (fewer registers necessary).
If the example is taken of calculating the exponentiation, an algorithm for modular exponentiation of a number α by an exponent r based on the right to left processing (ARL) can be as follows:                There are applied, as inputs of the algorithm, a number α, and the signed binary representation (r′m, r′m−1, . . . , r′2, r′1, r′0).        The accumulator which contains the result M is initialised to 1, that is to say M=1.        A temporary register is initialised, which contains a calculation variable S with the number α to which the exponentiation is applied.        The following loop is implemented for i equals 0 up to i equals m−1:                    if r′i=1, the content M of the accumulator is multiplied by the variable S, and the result is loaded into the accumulator, which is written: M=M.S            if r′i=−1, the content M of the accumulator is multiplied by the inverse of the variable S, and the result is loaded into the accumulator, which is written M=M.S−1.                        
An algorithm for the modular exponentiation of the number a by the exponent r based on a left to right processing (ALR) of the exponent is as follows:                There are applied as inputs the number α, and the signed binary representation (r′m, r′m−1, . . . , r′2, r′1, r′0) of the exponent r.        The content M of the accumulator is initialised to 1: M=1.        For i equals m to i equals 0:                    the multiplication of the content of the accumulator by itself is performed and the accumulator is loaded with the result, which is written: M=M2, and then            if r′i=1, the content of the accumulator is multiplied by α and the result is loaded into the accumulator: M=M.α, or            if r′i=−1, the content of the accumulator is multiplied by the inverse of α and the result is loaded into the accumulator: M=M.α−1.                        
The right to left algorithm ARL therefore requires at least one additional register, for the variable S, than the left to right algorithm ALR. In addition, S being variable, it is necessary to calculate S−1 each time the associated condition is achieved in the right to left algorithm. In the left to right algorithm, α being determined (fixed), its inverse α−1 can be calculated only once and stored.
In the invention, it has been sought to combine the advantages of left to right processing both in the method of converting an operand and in the arithmetic processing using this operand.
Thus, in the invention, a signed binary representation equivalent to the Reitwiesner representation has been sought, that is to say a representation which has the same Hamming weight for the same length m (number of digits in the representation).